package q875_minEatingSpeed;

public class Solution {
    /*
    考虑速度的选择：
    首先题中已经规定了h >= length
    所以我们设定high为piles中的最大值 必然能够吃完所有的香蕉
    但是我们期望获得一个在h时间内吃完的最小speed 所以我们可以从low - high中
    利用二分查找 来找出一个speed 使得吃完所有的香蕉恰好达到h小时
    这题的关键在于理解 我们二分查找 是基于吃的速度而进行寻找 而不是在piles中设定一个值来寻找什么
     */
    public int minEatingSpeed(int[] piles, int h) {
        int low = 1, high = 0;
        for (int pile : piles) high = Math.max(high, pile);
        int ans = high;
        while (low < high) {
            int curSpeed = low + ((high - low) >> 1);
            long time = getTime(piles, curSpeed);
            if (time <= h) {
                ans = curSpeed;
                high = curSpeed;
            } else {
                low = curSpeed + 1;
            }
        }
        return ans;
    }
    public long getTime(int[] piles, int speed) {
        long time = 0;
        for (int pile : piles) {
            time += pile <= speed ? 1 : (pile + speed - 1)/ speed;
        }
        return time;
    }

}
